package leetcode.code1178;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	Node root;

	class Node {
		Node[] word;
		int count;

		public Node() {
			word = new Node[26];
		}

		public void add(String words) {
			char[] chars = words.toCharArray();
			Arrays.sort(chars);
			int index = chars[0] - 'a';
			if (root.word[index] == null) {
				root.word[index] = new Node();
			}
			Node node = root.word[index];
			for (int i = 1; i < chars.length; i++) {
				if (chars[i] != chars[i - 1]) {
					index = chars[i] - 'a';
					if (node.word[index] == null) {
						node.word[index] = new Node();
					}
					node = node.word[index];
				}
			}
			node.count += 1;
		}
	}

	public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
		root = new Node();
		for (String word : words) {
			root.add(word);
		}
		List<Integer> ans = new ArrayList<>();
		for (String puzzle2 : puzzles) {
			char[] puzzle = puzzle2.toCharArray();
			char first = puzzle[0];
			Arrays.sort(puzzle);
			int curAns = this.f(root, puzzle, 0, first);
			ans.add(curAns);
		}
		return ans;
	}

	/**
	 * 从Node开始，决定是否选择puzzle中index位置字符当作谜底中的字符。
	 */
	private int f(Node node, char[] puzzle, int index, char first) {
		if (node == null) {// 上一步选择的字符是不存在的，这个谜底不对，返回0
			return 0;
		}
		if (index == puzzle.length) {// 所有选择都做完，返回这个谜底的数量
			return node.count;
		}
		int ans = 0;
		char cur = puzzle[index];
		if (cur == first) {// 首字符必须选
			ans += this.f(node.word[cur - 'a'], puzzle, index + 1, first);
		} else {
			ans += this.f(node, puzzle, index + 1, first);// 可不选
			ans += this.f(node.word[cur - 'a'], puzzle, index + 1, first);// 可选
		}
		return ans;
	}

	@Override
	public void debug1() {
		List<Integer> e = HelpDebug.str2intlist("[1,1,3,2,4,0]");
		HelpDebug.compare(e,
				this.findNumOfValidWords(
						HelpDebug.str2array2("[\"aaaa\",\"asas\",\"able\",\"ability\",\"actt\",\"actor\",\"access\"]"),
						HelpDebug.str2array2("[\"aboveyz\",\"abrodyz\",\"abslute\",\"absoryz\",\"actresz\",\"gaswxyz\"]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();

	}

}
